// 全排列 2
// 方法 1
var dfs = function (nums, path, res, used) {
  if (path.length === nums.length) {
    res.push(path.slice())
    return
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue
    if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue
    path.push(nums[i])
    used[i] = true
    dfs(nums, path, res, used)
    path.pop()
    used[i] = false
  }
}
var permuteUnique = function (nums) {
  let res = []
  let path = []
  let used = new Array(nums.length).fill(false)
  nums.sort()
  dfs(nums, path, res, used)

  return res
}
// 方法 2 有问题，无法去重
var dfs = function (res, output, nums, first) {
  if (first === nums.length) {
    res.push(output.slice())
  }
  for (let i = first; i < nums.length; i++) {
    ;[output[first], output[i]] = [output[i], output[first]]
    dfs(res, output, nums, first + 1)
    ;[output[first], output[i]] = [output[i], output[first]]
  }
}

var permuteUnique = function (nums) {
  let res = []
  let output = []
  nums.sort()
  for (let k of nums) {
    output.push(k)
  }

  dfs(res, output, nums, 0)

  return res
}
